package com.yulongtian.weekCompetition.month202211.week3;

import java.lang.annotation.Target;
import java.util.ArrayList;
import java.util.List;

/**
 * 超时   还差3个用例
 *
 * @author yulongTian
 * @create 2022-11-20 10:38
 */
public class Test02 {
    public static void main(String[] args) {
        TreeNode root6 = new TreeNode(6);
        TreeNode root1 = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        TreeNode root4 = new TreeNode(4);
        TreeNode root9 = new TreeNode(9);
        TreeNode root13 = new TreeNode(13);
        TreeNode root14 = new TreeNode(14);
        TreeNode root15 = new TreeNode(15);

        root6.left = root2;
        root6.right = root13;
        root2.left = root1;
        root2.right = root4;
        root13.left = root9;
        root13.right = root15;
        root15.left = root14;

        List<Integer> queries = new ArrayList<>();
        queries.add(2);
        queries.add(5);
        queries.add(16);
        List<List<Integer>> lists = closestNodes(root6, queries);
        if (lists != null) {
            System.out.println(lists.toString());
        }


    }

    public static List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        List<List<Integer>> res = new ArrayList<>();

        List<Integer> arr = new ArrayList<>();
        dfs(root, arr);

        for (Integer query : queries) {
            if (query < arr.get(0)) {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(-1);
                temp.add(arr.get(0));
                res.add(temp);
                continue;
            }
            if (query > arr.get(arr.size() - 1)) {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(arr.get(arr.size() - 1));
                temp.add(-1);
                res.add(temp);
                continue;
            }
            if (arr.contains(query)) {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(query);
                temp.add(query);
                res.add(temp);
                continue;
            }

            //遍历中间 二分查找?
//            for (int i = 1; i < arr.size(); i++) {
//                if (query > arr.get(i - 1) && query < arr.get(i)) {
//                    ArrayList<Integer> temp = new ArrayList<>();
//                    temp.add(arr.get(i - 1));
//                    temp.add(arr.get(i));
//                    res.add(temp);
//                    break;
//                }
//            }

            int left = 0;
            int right = arr.size() - 1;

            while (left < right) {
                int mid = (left + right) / 2;
                if (arr.get(mid) > query) {
                    right = mid - 1;
                }
                if (arr.get(mid) < query) {
                    left = mid + 1;
                }
            }

            System.out.println(query);
            System.out.println(left);
            System.out.println(right);
            System.out.println("---------------");

            //附近遍历
            int mid = (left + right) / 2;
            if(arr.get(mid)<query){
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(arr.get(mid));
                temp.add(arr.get(mid+1));
                res.add(temp);
            }else{
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(arr.get(mid-1));
                temp.add(arr.get(mid));
                res.add(temp);
            }


        }

        return res;
    }

    //中序遍历
    public static void dfs(TreeNode root, List<Integer> arr) {
        if (root == null) {
            return;
        }

        //左
        if (root.left != null) {
            dfs(root.left, arr);
        }
        //根
//        System.out.println(root.val);
        arr.add(root.val);

        //右
        if (root.right != null) {
            dfs(root.right, arr);
        }
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
